1 /**
  2  * The top-level Protovis namespace. All public methods and fields should be
  3  * registered on this object. Note that core Protovis source is surrounded by an
  4  * anonymous function, so any other declared globals will not be visible outside
  5  * of core methods. This also allows multiple versions of Protovis to coexist,
  6  * since each version will see their own <tt>pv</tt> namespace.
  7  *
  8  * @namespace The top-level Protovis namespace, <tt>pv</tt>.
  9  */
 10 var pv = {};
 11 
 12 /**
 13  * @private Returns a prototype object suitable for extending the given class
 14  * <tt>f</tt>. Rather than constructing a new instance of <tt>f</tt> to serve as
 15  * the prototype (which unnecessarily runs the constructor on the created
 16  * prototype object, potentially polluting it), an anonymous function is
 17  * generated internally that shares the same prototype:
 18  *
 19  * <pre>function g() {}
 20  * g.prototype = f.prototype;
 21  * return new g();</pre>
 22  *
 23  * For more details, see Douglas Crockford's essay on prototypal inheritance.
 24  *
 25  * @param {function} f a constructor.
 26  * @returns a suitable prototype object.
 27  * @see Douglas Crockford's essay on <a
 28  * href="http://javascript.crockford.com/prototypal.html">prototypal
 29  * inheritance</a>.
 30  */
 31 pv.extend = function(f) {
 32   function g() {}
 33   g.prototype = f.prototype || f;
 34   return new g();
 35 };
 36 
 37 try {
 38   eval("pv.parse = function(x) x;"); // native support
 39 } catch (e) {
 40 
 41 /**
 42  * @private Parses a Protovis specification, which may use JavaScript 1.8
 43  * function expresses, replacing those function expressions with proper
 44  * functions such that the code can be run by a JavaScript 1.6 interpreter. This
 45  * hack only supports function expressions (using clumsy regular expressions, no
 46  * less), and not other JavaScript 1.8 features such as let expressions.
 47  *
 48  * @param {string} s a Protovis specification (i.e., a string of JavaScript 1.8
 49  * source code).
 50  * @returns {string} a conformant JavaScript 1.6 source code.
 51  */
 52   pv.parse = function(js) { // hacky regex support
 53     var re = new RegExp("function(\\s+\\w+)?\\([^)]*\\)\\s*", "mg"), m, d, i = 0, s = "";
 54     while (m = re.exec(js)) {
 55       var j = m.index + m[0].length;
 56       if (js.charAt(j--) != '{') {
 57         s += js.substring(i, j) + "{return ";
 58         i = j;
 59         for (var p = 0; p >= 0 && j < js.length; j++) {
 60           var c = js.charAt(j);
 61           switch (c) {
 62             case '"': case '\'': {
 63               while (++j < js.length && (d = js.charAt(j)) != c) {
 64                 if (d == '\\') j++;
 65               }
 66               break;
 67             }
 68             case '[': case '(': p++; break;
 69             case ']': case ')': p--; break;
 70             case ';':
 71             case ',': if (p == 0) p--; break;
 72           }
 73         }
 74         s += pv.parse(js.substring(i, --j)) + ";}";
 75         i = j;
 76       }
 77       re.lastIndex = j;
 78     }
 79     s += js.substring(i);
 80     return s;
 81   };
 82 }
 83 
 84 /**
 85  * Returns the passed-in argument, <tt>x</tt>; the identity function. This method
 86  * is provided for convenience since it is used as the default behavior for a
 87  * number of property functions.
 88  *
 89  * @param x a value.
 90  * @returns the value <tt>x</tt>.
 91  */
 92 pv.identity = function(x) { return x; };
 93 
 94 /**
 95  * Returns <tt>this.index</tt>. This method is provided for convenience for use
 96  * with scales. For example, to color bars by their index, say:
 97  *
 98  * <pre>.fillStyle(pv.Colors.category10().by(pv.index))</pre>
 99  *
100  * This method is equivalent to <tt>function() this.index</tt>, but more
101  * succinct. Note that the <tt>index</tt> property is also supported for
102  * accessor functions with {@link pv.max}, {@link pv.min} and other array
103  * utility methods.
104  *
105  * @see pv.Scale
106  * @see pv.Mark#index
107  */
108 pv.index = function() { return this.index; };
109 
110 /**
111  * Returns <tt>this.childIndex</tt>. This method is provided for convenience for
112  * use with scales. For example, to color bars by their child index, say:
113  *
114  * <pre>.fillStyle(pv.Colors.category10().by(pv.child))</pre>
115  *
116  * This method is equivalent to <tt>function() this.childIndex</tt>, but more
117  * succinct.
118  *
119  * @see pv.Scale
120  * @see pv.Mark#childIndex
121  */
122 pv.child = function() { return this.childIndex; };
123 
124 /**
125  * Returns <tt>this.parent.index</tt>. This method is provided for convenience
126  * for use with scales. This method is provided for convenience for use with
127  * scales. For example, to color bars by their parent index, say:
128  *
129  * <pre>.fillStyle(pv.Colors.category10().by(pv.parent))</pre>
130  *
131  * Tthis method is equivalent to <tt>function() this.parent.index</tt>, but more
132  * succinct.
133  *
134  * @see pv.Scale
135  * @see pv.Mark#index
136  */
137 pv.parent = function() { return this.parent.index; };
138 
139 /**
140  * Returns an array of numbers, starting at <tt>start</tt>, incrementing by
141  * <tt>step</tt>, until <tt>stop</tt> is reached. The stop value is exclusive. If
142  * only a single argument is specified, this value is interpeted as the
143  * <i>stop</i> value, with the <i>start</i> value as zero. If only two arguments
144  * are specified, the step value is implied to be one.
145  *
146  * <p>The method is modeled after the built-in <tt>range</tt> method from
147  * Python. See the Python documentation for more details.
148  *
149  * @see <a href="http://docs.python.org/library/functions.html#range">Python range</a>
150  * @param {number} [start] the start value.
151  * @param {number} stop the stop value.
152  * @param {number} [step] the step value.
153  * @returns {number[]} an array of numbers.
154  */
155 pv.range = function(start, stop, step) {
156   if (arguments.length == 1) {
157     stop = start;
158     start = 0;
159   }
160   if (step == undefined) step = 1;
161   else if (!step) throw new Error("step must be non-zero");
162   var array = [], i = 0, j;
163   if (step < 0) {
164     while ((j = start + step * i++) > stop) {
165       array.push(j);
166     }
167   } else {
168     while ((j = start + step * i++) < stop) {
169       array.push(j);
170     }
171   }
172   return array;
173 };
174 
175 /**
176  * Returns a random number in the range [<tt>min</tt>, <tt>max</tt>) that is a
177  * multiple of <tt>step</tt>. More specifically, the returned number is of the
178  * form <tt>min</tt> + <i>n</i> * <tt>step</tt>, where <i>n</i> is a nonnegative
179  * integer. If <tt>step</tt> is not specified, it defaults to 1, returning a
180  * random integer if <tt>min</tt> is also an integer.
181  *
182  * @param min {number} minimum value.
183  * @param [max] {number} maximum value.
184  * @param [step] {numbeR} step value.
185  */
186 pv.random = function(min, max, step) {
187   if (arguments.length == 1) {
188     max = min;
189     min = 0;
190   }
191   if (step == undefined) {
192     step = 1;
193   }
194   return step
195       ? (Math.floor(Math.random() * (max - min) / step) * step + min)
196       : (Math.random() * (max - min) + min);
197 };
198 
199 /**
200  * Concatenates the specified array with itself <i>n</i> times. For example,
201  * <tt>pv.repeat([1, 2])</tt> returns [1, 2, 1, 2].
202  *
203  * @param {array} a an array.
204  * @param {number} [n] the number of times to repeat; defaults to two.
205  * @returns {array} an array that repeats the specified array.
206  */
207 pv.repeat = function(array, n) {
208   if (arguments.length == 1) n = 2;
209   return pv.blend(pv.range(n).map(function() { return array; }));
210 };
211 
212 /**
213  * Given two arrays <tt>a</tt> and <tt>b</tt>, <style
214  * type="text/css">sub{line-height:0}</style> returns an array of all possible
215  * pairs of elements [a<sub>i</sub>, b<sub>j</sub>]. The outer loop is on array
216  * <i>a</i>, while the inner loop is on <i>b</i>, such that the order of
217  * returned elements is [a<sub>0</sub>, b<sub>0</sub>], [a<sub>0</sub>,
218  * b<sub>1</sub>], ... [a<sub>0</sub>, b<sub>m</sub>], [a<sub>1</sub>,
219  * b<sub>0</sub>], [a<sub>1</sub>, b<sub>1</sub>], ... [a<sub>1</sub>,
220  * b<sub>m</sub>], ... [a<sub>n</sub>, b<sub>m</sub>]. If either array is empty,
221  * an empty array is returned.
222  *
223  * @param {array} a an array.
224  * @param {array} b an array.
225  * @returns {array} an array of pairs of elements in <tt>a</tt> and <tt>b</tt>.
226  */
227 pv.cross = function(a, b) {
228   var array = [];
229   for (var i = 0, n = a.length, m = b.length; i < n; i++) {
230     for (var j = 0, x = a[i]; j < m; j++) {
231       array.push([x, b[j]]);
232     }
233   }
234   return array;
235 };
236 
237 /**
238  * Given the specified array of arrays, concatenates the arrays into a single
239  * array. If the individual arrays are explicitly known, an alternative to blend
240  * is to use JavaScript's <tt>concat</tt> method directly. These two equivalent
241  * expressions:<ul>
242  *
243  * <li><tt>pv.blend([[1, 2, 3], ["a", "b", "c"]])</tt>
244  * <li><tt>[1, 2, 3].concat(["a", "b", "c"])</tt>
245  *
246  * </ul>return [1, 2, 3, "a", "b", "c"].
247  *
248  * @param {array[]} arrays an array of arrays.
249  * @returns {array} an array containing all the elements of each array in
250  * <tt>arrays</tt>.
251  */
252 pv.blend = function(arrays) {
253   return Array.prototype.concat.apply([], arrays);
254 };
255 
256 /**
257  * Given the specified array of arrays, <style
258  * type="text/css">sub{line-height:0}</style> transposes each element
259  * array<sub>ij</sub> with array<sub>ji</sub>. If the array has dimensions
260  * <i>n</i>×<i>m</i>, it will have dimensions <i>m</i>×<i>n</i>
261  * after this method returns. This method transposes the elements of the array
262  * in place, mutating the array, and returning a reference to the array.
263  *
264  * @param {array[]} arrays an array of arrays.
265  * @returns {array[]} the passed-in array, after transposing the elements.
266  */
267 pv.transpose = function(arrays) {
268   var n = arrays.length, m = pv.max(arrays, function(d) { return d.length; });
269 
270   if (m > n) {
271     arrays.length = m;
272     for (var i = n; i < m; i++) {
273       arrays[i] = new Array(n);
274     }
275     for (var i = 0; i < n; i++) {
276       for (var j = i + 1; j < m; j++) {
277         var t = arrays[i][j];
278         arrays[i][j] = arrays[j][i];
279         arrays[j][i] = t;
280       }
281     }
282   } else {
283     for (var i = 0; i < m; i++) {
284       arrays[i].length = n;
285     }
286     for (var i = 0; i < n; i++) {
287       for (var j = 0; j < i; j++) {
288         var t = arrays[i][j];
289         arrays[i][j] = arrays[j][i];
290         arrays[j][i] = t;
291       }
292     }
293   }
294 
295   arrays.length = m;
296   for (var i = 0; i < m; i++) {
297     arrays[i].length = n;
298   }
299 
300   return arrays;
301 };
302 
303 /**
304  * Returns all of the property names (keys) of the specified object (a map). The
305  * order of the returned array is not defined.
306  *
307  * @param map an object.
308  * @returns {string[]} an array of strings corresponding to the keys.
309  * @see #entries
310  */
311 pv.keys = function(map) {
312   var array = [];
313   for (var key in map) {
314     array.push(key);
315   }
316   return array;
317 };
318 
319 /**
320  * Returns all of the entries (key-value pairs) of the specified object (a
321  * map). The order of the returned array is not defined. Each key-value pair is
322  * represented as an object with <tt>key</tt> and <tt>value</tt> attributes,
323  * e.g., <tt>{key: "foo", value: 42}</tt>.
324  *
325  * @param map an object.
326  * @returns {array} an array of key-value pairs corresponding to the keys.
327  */
328 pv.entries = function(map) {
329   var array = [];
330   for (var key in map) {
331     array.push({ key: key, value: map[key] });
332   }
333   return array;
334 };
335 
336 /**
337  * Returns all of the values (attribute values) of the specified object (a
338  * map). The order of the returned array is not defined.
339  *
340  * @param map an object.
341  * @returns {array} an array of objects corresponding to the values.
342  * @see #entries
343  */
344 pv.values = function(map) {
345   var array = [];
346   for (var key in map) {
347     array.push(map[key]);
348   }
349   return array;
350 };
351 
352 /**
353  * @private A private variant of Array.prototype.map that supports the index
354  * property.
355  */
356 function map(array, f) {
357   var o = {};
358   return f
359       ? array.map(function(d, i) { o.index = i; return f.call(o, d); })
360       : array.slice();
361 };
362 
363 /**
364  * Returns a normalized copy of the specified array, such that the sum of the
365  * returned elements sum to one. If the specified array is not an array of
366  * numbers, an optional accessor function <tt>f</tt> can be specified to map the
367  * elements to numbers. For example, if <tt>array</tt> is an array of objects,
368  * and each object has a numeric property "foo", the expression
369  *
370  * <pre>pv.normalize(array, function(d) d.foo)</pre>
371  *
372  * returns a normalized array on the "foo" property. If an accessor function is
373  * not specified, the identity function is used. Accessor functions can refer to
374  * <tt>this.index</tt>.
375  *
376  * @param {array} array an array of objects, or numbers.
377  * @param {function} [f] an optional accessor function.
378  * @returns {number[]} an array of numbers that sums to one.
379  */
380 pv.normalize = function(array, f) {
381   var norm = map(array, f), sum = pv.sum(norm);
382   for (var i = 0; i < norm.length; i++) norm[i] /= sum;
383   return norm;
384 };
385 
386 /**
387  * Returns the sum of the specified array. If the specified array is not an
388  * array of numbers, an optional accessor function <tt>f</tt> can be specified
389  * to map the elements to numbers. See {@link #normalize} for an example.
390  * Accessor functions can refer to <tt>this.index</tt>.
391  *
392  * @param {array} array an array of objects, or numbers.
393  * @param {function} [f] an optional accessor function.
394  * @returns {number} the sum of the specified array.
395  */
396 pv.sum = function(array, f) {
397   var o = {};
398   return array.reduce(f
399       ? function(p, d, i) { o.index = i; return p + f.call(o, d); }
400       : function(p, d) { return p + d; }, 0);
401 };
402 
403 /**
404  * Returns the maximum value of the specified array. If the specified array is
405  * not an array of numbers, an optional accessor function <tt>f</tt> can be
406  * specified to map the elements to numbers. See {@link #normalize} for an
407  * example. Accessor functions can refer to <tt>this.index</tt>.
408  *
409  * @param {array} array an array of objects, or numbers.
410  * @param {function} [f] an optional accessor function.
411  * @returns {number} the maximum value of the specified array.
412  */
413 pv.max = function(array, f) {
414   if (f == pv.index) return array.length - 1;
415   return Math.max.apply(null, f ? map(array, f) : array);
416 };
417 
418 /**
419  * Returns the index of the maximum value of the specified array. If the
420  * specified array is not an array of numbers, an optional accessor function
421  * <tt>f</tt> can be specified to map the elements to numbers. See
422  * {@link #normalize} for an example. Accessor functions can refer to
423  * <tt>this.index</tt>.
424  *
425  * @param {array} array an array of objects, or numbers.
426  * @param {function} [f] an optional accessor function.
427  * @returns {number} the index of the maximum value of the specified array.
428  */
429 pv.max.index = function(array, f) {
430   if (f == pv.index) return array.length - 1;
431   if (!f) f = pv.identity;
432   var maxi = -1, maxx = -Infinity, o = {};
433   for (var i = 0; i < array.length; i++) {
434     o.index = i;
435     var x = f.call(o, array[i]);
436     if (x > maxx) {
437       maxx = x;
438       maxi = i;
439     }
440   }
441   return maxi;
442 }
443 
444 /**
445  * Returns the minimum value of the specified array of numbers. If the specified
446  * array is not an array of numbers, an optional accessor function <tt>f</tt>
447  * can be specified to map the elements to numbers. See {@link #normalize} for
448  * an example. Accessor functions can refer to <tt>this.index</tt>.
449  *
450  * @param {array} array an array of objects, or numbers.
451  * @param {function} [f] an optional accessor function.
452  * @returns {number} the minimum value of the specified array.
453  */
454 pv.min = function(array, f) {
455   if (f == pv.index) return 0;
456   return Math.min.apply(null, f ? map(array, f) : array);
457 };
458 
459 /**
460  * Returns the index of the minimum value of the specified array. If the
461  * specified array is not an array of numbers, an optional accessor function
462  * <tt>f</tt> can be specified to map the elements to numbers. See
463  * {@link #normalize} for an example. Accessor functions can refer to
464  * <tt>this.index</tt>.
465  *
466  * @param {array} array an array of objects, or numbers.
467  * @param {function} [f] an optional accessor function.
468  * @returns {number} the index of the minimum value of the specified array.
469  */
470 pv.min.index = function(array, f) {
471   if (f == pv.index) return 0;
472   if (!f) f = pv.identity;
473   var mini = -1, minx = Infinity, o = {};
474   for (var i = 0; i < array.length; i++) {
475     o.index = i;
476     var x = f.call(o, array[i]);
477     if (x < minx) {
478       minx = x;
479       mini = i;
480     }
481   }
482   return mini;
483 }
484 
485 /**
486  * Returns the arithmetic mean, or average, of the specified array. If the
487  * specified array is not an array of numbers, an optional accessor function
488  * <tt>f</tt> can be specified to map the elements to numbers. See
489  * {@link #normalize} for an example. Accessor functions can refer to
490  * <tt>this.index</tt>.
491  *
492  * @param {array} array an array of objects, or numbers.
493  * @param {function} [f] an optional accessor function.
494  * @returns {number} the mean of the specified array.
495  */
496 pv.mean = function(array, f) {
497   return pv.sum(array, f) / array.length;
498 };
499 
500 /**
501  * Returns the median of the specified array. If the specified array is not an
502  * array of numbers, an optional accessor function <tt>f</tt> can be specified
503  * to map the elements to numbers. See {@link #normalize} for an example.
504  * Accessor functions can refer to <tt>this.index</tt>.
505  *
506  * @param {array} array an array of objects, or numbers.
507  * @param {function} [f] an optional accessor function.
508  * @returns {number} the median of the specified array.
509  */
510 pv.median = function(array, f) {
511   if (f == pv.index) return (array.length - 1) / 2;
512   array = map(array, f).sort(pv.naturalOrder);
513   if (array.length % 2) return array[Math.floor(array.length / 2)];
514   var i = array.length / 2;
515   return (array[i - 1] + array[i]) / 2;
516 };
517 
518 /**
519  * Returns a map constructed from the specified <tt>keys</tt>, using the
520  * function <tt>f</tt> to compute the value for each key. The single argument to
521  * the value function is the key. The callback is invoked only for indexes of
522  * the array which have assigned values; it is not invoked for indexes which
523  * have been deleted or which have never been assigned values.
524  *
525  * <p>For example, this expression creates a map from strings to string length:
526  *
527  * <pre>pv.dict(["one", "three", "seventeen"], function(s) s.length)</pre>
528  *
529  * The returned value is <tt>{one: 3, three: 5, seventeen: 9}</tt>. Accessor
530  * functions can refer to <tt>this.index</tt>.
531  *
532  * @param {array} keys an array.
533  * @param {function} f a value function.
534  * @returns a map from keys to values.
535  */
536 pv.dict = function(keys, f) {
537   var m = {}, o = {};
538   for (var i = 0; i < keys.length; i++) {
539     if (i in keys) {
540       var k = keys[i];
541       o.index = i;
542       m[k] = f.call(o, k);
543     }
544   }
545   return m;
546 };
547 
548 /**
549  * Returns a permutation of the specified array, using the specified array of
550  * indexes. The returned array contains the corresponding element in
551  * <tt>array</tt> for each index in <tt>indexes</tt>, in order. For example,
552  *
553  * <pre>pv.permute(["a", "b", "c"], [1, 2, 0])</pre>
554  *
555  * returns <tt>["b", "c", "a"]</tt>. It is acceptable for the array of indexes
556  * to be a different length from the array of elements, and for indexes to be
557  * duplicated or omitted. The optional accessor function <tt>f</tt> can be used
558  * to perform a simultaneous mapping of the array elements. Accessor functions
559  * can refer to <tt>this.index</tt>.
560  *
561  * @param {array} array an array.
562  * @param {number[]} indexes an array of indexes into <tt>array</tt>.
563  * @param {function} [f] an optional accessor function.
564  * @returns {array} an array of elements from <tt>array</tt>; a permutation.
565  */
566 pv.permute = function(array, indexes, f) {
567   if (!f) f = pv.identity;
568   var p = new Array(indexes.length), o = {};
569   indexes.forEach(function(j, i) { o.index = j; p[i] = f.call(o, array[j]); });
570   return p;
571 };
572 
573 /**
574  * Returns a map from key to index for the specified <tt>keys</tt> array. For
575  * example,
576  *
577  * <pre>pv.numerate(["a", "b", "c"])</pre>
578  *
579  * returns <tt>{a: 0, b: 1, c: 2}</tt>. Note that since JavaScript maps only
580  * support string keys, <tt>keys</tt> must contain strings, or other values that
581  * naturally map to distinct string values. Alternatively, an optional accessor
582  * function <tt>f</tt> can be specified to compute the string key for the given
583  * element. Accessor functions can refer to <tt>this.index</tt>.
584  *
585  * @param {array} keys an array, usually of string keys.
586  * @param {function} [f] an optional key function.
587  * @returns a map from key to index.
588  */
589 pv.numerate = function(keys, f) {
590   if (!f) f = pv.identity;
591   var map = {}, o = {};
592   keys.forEach(function(x, i) { o.index = i; map[f.call(o, x)] = i; });
593   return map;
594 };
595 
596 /**
597  * The comparator function for natural order. This can be used in conjunction with
598  * the built-in array <tt>sort</tt> method to sort elements by their natural
599  * order, ascending. Note that if no comparator function is specified to the
600  * built-in <tt>sort</tt> method, the default order is lexicographic, <i>not</i>
601  * natural!
602  *
603  * @see <a
604  * href="http://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort">Array.sort</a>.
605  * @param a an element to compare.
606  * @param b an element to compare.
607  * @returns {number} negative if a < b; positive if a > b; otherwise 0.
608  */
609 pv.naturalOrder = function(a, b) {
610   return (a < b) ? -1 : ((a > b) ? 1 : 0);
611 };
612 
613 /**
614  * The comparator function for reverse natural order. This can be used in
615  * conjunction with the built-in array <tt>sort</tt> method to sort elements by
616  * their natural order, descending. Note that if no comparator function is
617  * specified to the built-in <tt>sort</tt> method, the default order is
618  * lexicographic, <i>not</i> natural!
619  *
620  * @see #naturalOrder
621  * @param a an element to compare.
622  * @param b an element to compare.
623  * @returns {number} negative if a < b; positive if a > b; otherwise 0.
624  */
625 pv.reverseOrder = function(b, a) {
626   return (a < b) ? -1 : ((a > b) ? 1 : 0);
627 };
628 
629 /**
630  * @private Computes the value of the specified CSS property <tt>p</tt> on the
631  * specified element <tt>e</tt>.
632  *
633  * @param {string} p the name of the CSS property.
634  * @param e the element on which to compute the CSS property.
635  */
636 pv.css = function(e, p) {
637   return window.getComputedStyle
638       ? window.getComputedStyle(e, null).getPropertyValue(p)
639       : e.currentStyle[p];
640 };
641 
642 /**
643  * Namespace constants for SVG, XMLNS, and XLINK.
644  *
645  * @namespace Namespace constants for SVG, XMLNS, and XLINK.
646  */
647 pv.ns = {
648   /**
649    * The SVG namespace, "http://www.w3.org/2000/svg".
650    *
651    * @type string
652    * @constant
653    */
654   svg: "http://www.w3.org/2000/svg",
655 
656   /**
657    * The XMLNS namespace, "http://www.w3.org/2000/xmlns".
658    *
659    * @type string
660    * @constant
661    */
662   xmlns: "http://www.w3.org/2000/xmlns",
663 
664   /**
665    * The XLINK namespace, "http://www.w3.org/1999/xlink".
666    *
667    * @type string
668    * @constant
669    */
670   xlink: "http://www.w3.org/1999/xlink"
671 };
672 
673 /**
674  * Protovis major and minor version numbers.
675  *
676  * @namespace Protovis major and minor version numbers.
677  */
678 pv.version = {
679   /**
680    * The major version number.
681    *
682    * @type number
683    * @constant
684    */
685   major: 3,
686 
687   /**
688    * The minor version number.
689    *
690    * @type number
691    * @constant
692    */
693   minor: 1
694 };
695 
696 /**
697  * @private Reports the specified error to the JavaScript console. Mozilla only
698  * allows logging to the console for privileged code; if the console is
699  * unavailable, the alert dialog box is used instead.
700  *
701  * @param e the exception that triggered the error.
702  */
703 pv.error = function(e) {
704   (typeof console == "undefined") ? alert(e) : console.error(e);
705 };
706 
707 /**
708  * @private Registers the specified listener for events of the specified type on
709  * the specified target. For standards-compliant browsers, this method uses
710  * <tt>addEventListener</tt>; for Internet Explorer, <tt>attachEvent</tt>.
711  *
712  * @param target a DOM element.
713  * @param {string} type the type of event, such as "click".
714  * @param {function} the listener callback function.
715  */
716 pv.listen = function(target, type, listener) {
717   return target.addEventListener
718     ? target.addEventListener(type, listener, false)
719     : target.attachEvent("on" + type, listener);
720 };
721 
722 /**
723  * Returns the logarithm with a given base value.
724  *
725  * @param {number} x the number for which to compute the logarithm.
726  * @param {number} b the base of the logarithm.
727  * @returns {number} the logarithm value.
728  */
729 pv.log = function(x, b) {
730   return Math.log(x) / Math.log(b);
731 };
732 
733 /**
734  * Computes a zero-symmetric logarithm. Computes the logarithm of the absolute
735  * value of the input, and determines the sign of the output according to the
736  * sign of the input value.
737  *
738  * @param {number} x the number for which to compute the logarithm.
739  * @param {number} b the base of the logarithm.
740  * @returns {number} the symmetric log value.
741  */
742 pv.logSymmetric = function(x, b) {
743   return (x == 0) ? 0 : ((x < 0) ? -pv.log(-x, b) : pv.log(x, b));
744 };
745 
746 /**
747  * Computes a zero-symmetric logarithm, with adjustment to values between zero
748  * and the logarithm base. This adjustment introduces distortion for values less
749  * than the base number, but enables simultaneous plotting of log-transformed
750  * data involving both positive and negative numbers.
751  *
752  * @param {number} x the number for which to compute the logarithm.
753  * @param {number} b the base of the logarithm.
754  * @returns {number} the adjusted, symmetric log value.
755  */
756 pv.logAdjusted = function(x, b) {
757   var negative = x < 0;
758   if (x < b) x += (b - x) / b;
759   return negative ? -pv.log(x, b) : pv.log(x, b);
760 };
761 
762 /**
763  * Rounds an input value down according to its logarithm. The method takes the
764  * floor of the logarithm of the value and then uses the resulting value as an
765  * exponent for the base value.
766  *
767  * @param {number} x the number for which to compute the logarithm floor.
768  * @param {number} b the base of the logarithm.
769  * @return {number} the rounded-by-logarithm value.
770  */
771 pv.logFloor = function(x, b) {
772   return (x > 0)
773       ? Math.pow(b, Math.floor(pv.log(x, b)))
774       : -Math.pow(b, -Math.floor(-pv.log(-x, b)));
775 };
776 
777 /**
778  * Rounds an input value up according to its logarithm. The method takes the
779  * ceiling of the logarithm of the value and then uses the resulting value as an
780  * exponent for the base value.
781  *
782  * @param {number} x the number for which to compute the logarithm ceiling.
783  * @param {number} b the base of the logarithm.
784  * @return {number} the rounded-by-logarithm value.
785  */
786 pv.logCeil = function(x, b) {
787   return (x > 0)
788       ? Math.pow(b, Math.ceil(pv.log(x, b)))
789       : -Math.pow(b, -Math.ceil(-pv.log(-x, b)));
790 };
791 
792 /**
793  * Searches the specified array of numbers for the specified value using the
794  * binary search algorithm. The array must be sorted (as by the <tt>sort</tt>
795  * method) prior to making this call. If it is not sorted, the results are
796  * undefined. If the array contains multiple elements with the specified value,
797  * there is no guarantee which one will be found.
798  *
799  * <p>The <i>insertion point</i> is defined as the point at which the value
800  * would be inserted into the array: the index of the first element greater than
801  * the value, or <tt>array.length</tt>, if all elements in the array are less
802  * than the specified value. Note that this guarantees that the return value
803  * will be nonnegative if and only if the value is found.
804  *
805  * @param {number[]} array the array to be searched.
806  * @param {number} value the value to be searched for.
807  * @returns the index of the search value, if it is contained in the array;
808  * otherwise, (-(<i>insertion point</i>) - 1).
809  * @param {function} [f] an optional key function.
810  */
811 pv.search = function(array, value, f) {
812   if (!f) f = pv.identity;
813   var low = 0, high = array.length - 1;
814   while (low <= high) {
815     var mid = (low + high) >> 1, midValue = f(array[mid]);
816     if (midValue < value) low = mid + 1;
817     else if (midValue > value) high = mid - 1;
818     else return mid;
819   }
820   return -low - 1;
821 };
822 
823 pv.search.index = function(array, value, f) {
824   var i = pv.search(array, value, f);
825   return (i < 0) ? (-i - 1) : i;
826 };
827